package com.zlp.partice;

import org.junit.Test;

import java.util.*;

/**
 * @Author: zhulaiping
 * @Date: 2021/10/27 14:05
 */
public class Day20211027 {



    Set<String> set;
    public List<String> removeInvalidParentheses(String s) {
        int l=0,r=0;
        for (int i=0;i<s.length();i++){
            if(s.charAt(i)!='(' && s.charAt(i)!=')') continue;
            if(s.charAt(i) == '(') l++;
            else {
                if(l>0) l--;
                else r++;
            }
        }
        set = new HashSet<>();
        dfs(l,r,s,s.toCharArray(),0);
        return new ArrayList<>(set);
    }

    private void dfs(int l, int r, String s, char[] arr, int start) {
        if(l == 0 && r == 0){
            isValid(arr);
            return;
        }
        for (int i=start;i<s.length();i++){
            if(s.charAt(i)!='('&&s.charAt(i)!=')') continue;
            arr[i] = 'A';
            if(s.charAt(i)=='('){
                if(l > 0) dfs(l-1,r,s,arr,i+1);
            }else {
                if(r>0) dfs(l,r-1,s,arr,i+1);
            }
            arr[i] = s.charAt(i);
        }
    }

    private void isValid(char[] arr) {
        int l=0,r=0;
        for (int i=0;i<arr.length;i++){
            if(arr[i]!='('&&arr[i]!=')') continue;
            if(arr[i] == '(') l++;
            else {
                if(l>0) l--;
                else r++;
            }
        }
        if((l+r)==0) set.add(new String(arr).replaceAll("A",""));
    }




    public boolean reorderedPowerOf2(int n) {
        char[] arr = String.valueOf(n).toCharArray();
        boolean[] visited = new boolean[arr.length];
        return helper(arr,new StringBuilder(),visited,0);
    }

    private boolean helper(char[] arr, StringBuilder sb, boolean[] visited,int index) {
        if(index == arr.length){
            int value = Integer.parseInt(sb.toString());
            return (value&value-1) == 0 ? true : false;
        }
        boolean[] map = new boolean[10];
        for (int i=0;i<arr.length;i++){
            if(visited[i]) continue;
            if(index==0&&arr[i]=='0') continue;
            if(map[arr[i]-'0']) continue;
            map[arr[i]-'0'] = true;
            visited[i] = true;
            sb.append(arr[i]);
            if(helper(arr,sb, visited,index+1)) return true;
            sb.deleteCharAt(sb.length()-1);
            visited[i] = false;
        }
        return false;
    }
    @Test
    public void tt(){

        System.out.println(singleNumber(new int[]{1,2,1,3,2,5}));
    }
    public int[] singleNumber(int[] nums) {
        int[] ret = new int[2];
        int i = 0;
        Map<Integer,Integer>map = new HashMap<>(nums.length*2);
        for (int num:nums) map.put(num,map.getOrDefault(num,0)+1);
        for (int key:map.keySet()){
            if(map.get(key).equals(1)) ret[i++] = key;
            if(i==2) break;
        }
        return ret;
    }
    public int[] singleNumber2(int[] nums) {
        int temp = 0,a = 0, b = 0,bit = 1;
        for (int num:nums) temp ^= num;
        while ((bit&temp)==0) bit<<=1;
        for (int num:nums){
            if((num&bit) == 0) a ^= num;
            else b ^= num;
        }
        return new int[]{a,b};
    }
    public String[] findWords(String[] words) {
        Map<Character, Integer> map = new HashMap<>();
        String[] strs = new String[]{"QWERTYUIOPqwertyuiop", "ASDFGHJKLasdfghjkl", "ZXCVBNMzxcvbnm"};
        int i = 0;
        for (String str : strs) {
            for (char ch : str.toCharArray()) {
                map.put(ch, i);
            }
            i++;
        }
        return Arrays.stream(words).filter(o -> {
            int temp = o.charAt(0);
            for (char ch:o.toCharArray()) {
                if (map.get(ch)!=temp)
                    return false;
            }
            return true;
        }).toArray(String[]::new);
    }

    public int longestSubsequence(int[] arr, int difference) {
        int ret = 1,len = arr.length,cur;
        Map<Integer,Integer>map = new HashMap<>();
        for (int i=0;i<len;i++){
           cur = map.getOrDefault(arr[i]-difference,0)+1;
           if(cur>map.getOrDefault(arr[i],0)){
               map.put(arr[i],cur);
           }
           ret = Math.max(ret,cur);
        }
        return ret;
    }
    public int longestSubsequence2(int[] arr, int difference) {
        int ret = 1,cur;
        int[] map = new int[20001];
        for (int i=0;i<arr.length;i++){
            cur = map[arr[i]-difference+10000]+1;
            if(cur>map[arr[i]-difference+10000]){
                map[arr[i]+10000] = cur;
            }
            ret = Math.max(ret,cur);
        }
        return ret;
    }

    public String getHint(String secret, String guess) {
        int[] arr = new int[10],brr = new int[10];
        int a = 0,b = 0;
        for (int i=0;i<secret.length();i++){
            if(secret.charAt(i)==guess.charAt(i)){
                a++;
            }else {
                arr[secret.charAt(i)-'0']++;
                brr[guess.charAt((i))-'0']++;
            }
        }
        for (int i=0;i<10;i++){
            b += Math.min(arr[i],brr[i]);
        }
        return new StringBuilder(a).append("A").append(b).append("B").toString();
    }

    public String shortestCompletingWord(String licensePlate, String[] words) {
        int min = Integer.MAX_VALUE;
        String ret = null;
        Map<Character,Integer> map = getMap(licensePlate);
        for (String word:words){
            if(word.length()<min && indule(word,map)){
                min = Math.min(min,word.length());
                ret = word;
            }
        }
        return ret;
    }

    private Map<Character, Integer> getMap(String word) {
        Map<Character,Integer>map = new HashMap<>();
        for (char ch:word.toCharArray()){
            if(ch>='a'&&ch<='z'){
                map.put(ch,map.getOrDefault(ch,0)+1);
            }else if(ch>='A'&&ch<='Z'){
                ch += 32;
                map.put(ch,map.getOrDefault(ch,0)+1);
            }
        }
        return map;
    }

    private boolean indule(String word, Map<Character, Integer> map) {
        Map<Character, Integer> map1 = getMap(word);
        for (char ch:map.keySet()){
            if(map.get(ch)>map1.get(ch)){
                return false;
            }
        }
        return true;
    }
}
